package simple;


import data.ListNode;
import data.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/5/12 21:15
 */
public class No100_相同的树 {
    public static void main(String[] args) {
        Solution100 solution100 = new Solution100();
        TreeNode p = new TreeNode(1);
        p.left = new TreeNode(2);
        p.right = new TreeNode(3);

        TreeNode q = new TreeNode(1);
        q.left = new TreeNode(2);
        q.right = new TreeNode(3);
        boolean sameTree = solution100.isSameTree(p, q);
        System.out.println(sameTree);
    }
}

class Solution100 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //list
        List<TreeNode> list = new ArrayList<>();
        list.add(q);
        list.add(p);

        while (!list.isEmpty()) {
            TreeNode pTree = list.remove(list.size() - 1);
            TreeNode qTree = list.remove(list.size() - 1);
            if (pTree == null && qTree == null) {
                continue;
            }
            if (pTree == null || qTree == null) {
                return false;
            }
            if (pTree.val != qTree.val) {
                return false;
            } else {
                list.add(qTree.left);
                list.add(pTree.left);
                list.add(qTree.right);
                list.add(pTree.right);
            }
        }
        return true;

    }
}